#include <iostream>

using namespace std;

#define N 1000005

int a[N], dq[N], head, rear;

bool empty(){
    if (head == rear){
        return true;
    }
    return false;
}

bool push_front(int e){
    for (int i = rear; i > 1; i--){
        dq[i + 1] = dq[i];
    }
    dq[1] = e;
    rear++;
    return true;
}

bool push_back(int e){
    dq[++rear] = e;
    return true; 
}

bool pop_front(){
    for (int i = 1; i < rear; i++){
        dq[i] = dq[i + 1];
    }
    rear--;
    return 0;
}

bool pop_back(){
    rear--;
    return 0;
}

int front(){
    return dq[1];
}

int back(){
    return dq[rear];
}

int main(){
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++){
        while (!empty() && a[back()] > a[i]){
            pop_back();
        }
        push_back(i);

        if (i >= k){
            while (!empty() && front() <= i - k){
                pop_front();
            }

            cout << a[front()] << " ";
        }
    }

    cout << endl;

    while (!empty()){
        pop_front();
    }

    for (int i = 1; i <= n; i++){
        while (!empty() && a[back()] < a[i]){
            pop_back();
        }
        push_back(i);

        if (i >= k){
            while (!empty() && a[front()] <= i - k){
                pop_front();
            }

            cout << a[front()] << " ";
        }
    }

    return 0;
}